/*
 * ============================================================================
 * 数组 (Array) - C++ 实现（模板版）
 * ============================================================================
 * 
 * 【核心定义】
 * 数组是连续内存上的同类型元素集合；支持O(1)随机访问。
 * 本实现提供一个简化的动态数组 DynamicArray<T>，演示扩容/插入/删除等操作。
 * 
 * 【内存结构示意】（以int为例）
 *   data → |10|20|30|40|..cap..|
 *           ^              ^
 *          begin           capacity_end
 *   size 指向当前元素数目；capacity 为已分配但未必用完的空间。
 * 
 * 【复杂度】
 * - 访问: O(1)  - 通过偏移计算地址
 * - 尾部插入: 摊还 O(1)  - 扩容时 O(n)
 * - 中间插入/删除: O(n)  - 需移动元素
 * - 搜索: O(n)
 */

#include <iostream>
#include <stdexcept>
#include <initializer_list>
#include <cstring>  // std::memcpy
#include <string>

// 简化实现：要求T可拷贝
template <typename T>
class DynamicArray {
public:
    DynamicArray(size_t capacity = 8)
        : _size(0), _capacity(capacity), _data(new T[_capacity]) {}

    DynamicArray(std::initializer_list<T> init)
        : _size(init.size()), _capacity(std::max<size_t>(8, init.size())), _data(new T[_capacity]) {
        std::memcpy(_data, init.begin(), _size * sizeof(T));
    }

    ~DynamicArray() { delete[] _data; }

    size_t size() const { return _size; }
    size_t capacity() const { return _capacity; }
    bool empty() const { return _size == 0; }

    T& operator[](size_t index) {
        if (index >= _size) throw std::out_of_range("index out of range");
        return _data[index];
    }
    const T& operator[](size_t index) const {
        if (index >= _size) throw std::out_of_range("index out of range");
        return _data[index];
    }

    void push_back(const T& value) {
        ensure_capacity(_size + 1);
        _data[_size++] = value;
    }

    void insert(size_t index, const T& value) {
        if (index > _size) throw std::out_of_range("index out of range");
        ensure_capacity(_size + 1);
        // 后移 [index, _size-1]
        for (size_t i = _size; i > index; --i) _data[i] = _data[i - 1];
        _data[index] = value;
        ++_size;
    }

    void erase(size_t index) {
        if (index >= _size) throw std::out_of_range("index out of range");
        for (size_t i = index; i + 1 < _size; ++i) _data[i] = _data[i + 1];
        --_size;
    }

    void reserve(size_t new_cap) {
        if (new_cap <= _capacity) return;
        reallocate(new_cap);
    }

    void clear() { _size = 0; }

    void print(const std::string& prefix = "[") const {
        std::cout << prefix;
        for (size_t i = 0; i < _size; ++i) {
            std::cout << _data[i];
            if (i + 1 < _size) std::cout << ", ";
        }
        std::cout << "]\n";
    }

private:
    void ensure_capacity(size_t required) {
        if (required <= _capacity) return;
        size_t new_cap = _capacity * 2;
        while (new_cap < required) new_cap *= 2;
        reallocate(new_cap);
    }

    void reallocate(size_t new_cap) {
        T* new_data = new T[new_cap];
        for (size_t i = 0; i < _size; ++i) new_data[i] = _data[i];
        delete[] _data;
        _data = new_data;
        _capacity = new_cap;
    }

private:
    size_t _size;
    size_t _capacity;
    T* _data;
};

// 应用场景1：查找表（月份天数）
void example_lookup_table() {
    std::cout << "\n=== 应用场景1: 查找表 ===\n";
    int days_in_month[12] = {31,28,31,30,31,30,31,31,30,31,30,31};
    int month = 7; // 8月
    std::cout << "第" << (month + 1) << "个月有" << days_in_month[month] << "天\n";
}

// 应用场景2：简单缓存（键值表，演示数组存储结构）
struct CacheEntry { int key; int value; };
void example_cache() {
    std::cout << "\n=== 应用场景2: 简单缓存 ===\n";
    DynamicArray<CacheEntry> cache;
    cache.push_back({101, 500});
    cache.push_back({102, 600});

    int search_key = 101;
    for (size_t i = 0; i < cache.size(); ++i) {
        if (cache[i].key == search_key) {
            std::cout << "缓存命中: key=" << search_key << ", value=" << cache[i].value << "\n";
        }
    }
    std::cout << "优势: 连续内存，缓存友好，遍历快\n";
}

// 应用场景3：矩阵运算（图像处理示意）
void example_matrix() {
    std::cout << "\n=== 应用场景3: 矩阵运算 ===\n";
    int image[3][3] = {{255,200,150},{180,220,160},{140,190,210}};
    std::cout << "原始:\n";
    for (int i=0;i<3;++i){for(int j=0;j<3;++j) std::cout<<image[i][j]<<" "; std::cout<<"\n";}
    std::cout << "\n降低亮度后:\n";
    for (int i=0;i<3;++i){for(int j=0;j<3;++j){ image[i][j]=int(image[i][j]*0.8); std::cout<<image[i][j]<<" ";} std::cout<<"\n";}
}

int main() {
    std::cout << "╔════════════════════════════════════════╗\n";
    std::cout << "║   数组 (Array) - C++ 实现              ║\n";
    std::cout << "╚════════════════════════════════════════╝\n";

    std::cout << "\n--- 动态数组基本操作 ---\n";
    DynamicArray<int> arr;
    arr.push_back(10);
    arr.push_back(20);
    arr.push_back(30);
    arr.push_back(40);
    arr.print();

    std::cout << "在索引1插入25: ";
    arr.insert(1, 25); arr.print();

    std::cout << "删除索引2: ";
    arr.erase(2); arr.print();

    std::cout << "获取索引2: " << arr[2] << "\n";
    std::cout << "大小=" << arr.size() << ", 容量=" << arr.capacity() << "\n";

    example_lookup_table();
    example_cache();
    example_matrix();

    std::cout << "\n✅ 优势: O(1)随机访问, 连续内存, 缓存友好\n";
    std::cout << "⚠️ 局限: 中间插入/删除O(n), 需要扩容\n";
    return 0;
}
